package com.zjj.lbw.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhanglei.zjj
 * @description 基数排序
 * @date 2023/3/26 20:02
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] unsortedArr = new int[] {35, 23, 48, 9, 16, 24, 5, 11, 32, 17, 70, 56};
        radixSort(unsortedArr);
    }

    static void radixSort(int[] arr) {
        System.out.println("排序前的数组：" + Arrays.toString(arr));

        // 先找出最大值
        int max = arr[0];
        for (int item : arr) {
            if (item > max) {
                max = item;
            }
        }

        // 计算出位数，它决定有几轮排序
        int maxBit = 0;
        while (max != 0) {
            max /= 10;
            maxBit ++;
        }

        // 用list来做桶, 初始化
        List<List<Integer>> buckets = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }

        // 放入桶排序
        int mod = 10;
        int div = 1;
        for (int i = 0; i < maxBit; i++, mod *= 10, div *= 10) {
            for (int item : arr) {
                int index = (item % mod) / div;
                buckets.get(index).add(item);
            }

            // 将本轮结果刷回原数组，并清空桶，为下一轮准备好环境
            int index = 0;
            for (List<Integer> bucket : buckets) {
                for (Integer integer : bucket) {
                    arr[index] = integer;
                    index ++;
                }
            }
            for (List<Integer> bucket : buckets) {
                bucket.clear();
            }
        }

        // 排序结果
        System.out.println(Arrays.toString(arr));
    }
}
